from typing import List
import json

# 标签：字典树+数组+哈希表+字符串+排序
class Solution(object):
    # 多重遍历+排序
    def longestWord1(self, words):
        words.sort()
        words.sort(key=len, reverse=True)

        words_set = set(words)

        for w in words:
            flag = False
            for i in range(1, len(w)+1):
                if w[:i] not in words_set:
                    flag = False
                    break
                else:
                    flag = True
            if flag:
                return w
        return ''

    # 方法一：哈希集合
    def longestWord(self, words: List[str]) -> str:
        words.sort(key=lambda x: (-len(x), x), reverse=True)
        longest = ""
        candidates = {""}
        for word in words:
            if word[:-1] in candidates:
                longest = word
                candidates.add(word)
        return longest


# 方法二：字典树
class Trie:
    def __init__(self):
        self.children = [None] * 26
        self.isEnd = False

    def insert(self, word: str) -> None:
        node = self
        for ch in word:
            ch = ord(ch) - ord('a')
            if not node.children[ch]:
                node.children[ch] = Trie()
            node = node.children[ch]
        node.isEnd = True

    def search(self, word: str) -> bool:
        node = self
        for ch in word:
            ch = ord(ch) - ord('a')
            if node.children[ch] is None or not node.children[ch].isEnd:
                return False
            node = node.children[ch]
        return True

class Solution2:
    def longestWord(self, words: List[str]) -> str:
        t = Trie()
        for word in words:
            t.insert(word)
        longest = ""
        for word in words:
            if t.search(word) and (len(word) > len(longest) or len(word) == len(longest) and word < longest):
                longest = word
        return longest

# https://leetcode-cn.com/problems/longest-word-in-dictionary/